package com.jia.leetCode;

import java.util.*;

public class Pro0433 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> set = new HashSet<>();
        for (String b : bank) set.add(b);
        Map<String, Integer> map = new HashMap<>();
        map.put(startGene, 0);
        LinkedList<String> q = new LinkedList<>();
        q.offer(startGene);
        char[] cs = {'A', 'C', 'G', 'T'};
        while (!q.isEmpty()) {
            String t = q.poll();
            for (int i = 0; i < t.length(); i++) {
                for (int k = 0; k < 4; k++) {
                    char[] ss = t.toCharArray();
                    ss[i] = cs[k];
                    String newStr = String.valueOf(ss);
                    if (set.contains(newStr) && (!map.containsKey(newStr))) {
                        map.put(newStr, map.get(t) + 1);
                        q.offer(newStr);
                        if (newStr.equals(endGene)) {
                            return map.get(newStr);
                        }
                    }
                }
            }
        }
        return -1;
    }

}
